Data structures are organizations of data that permit a variety of ways to interact with the data stored therein. Data structures may be designed to permit efficient searches of the data, such as in a binary search tree, to permit efficient storage of sparse data, such as with a linked list, or to permit efficient storage of searchable data such as with a B-tree, among others.
Key-value data structures accept a key-value pair and are configured to respond to queries for the key. Key-value data structures may include such structures as dictionaries (e.g., maps, hash maps, etc.) in which the key is stored in a list that links (or contains) the respective value. While these structures are useful in-memory (e.g., in main or system state memory as opposed to storage), storage representations of these structures in persistent storage (e.g., on-disk) may be inefficient. Accordingly, a class of log-based storage structures have been introduced. An example is the log structured merge tree (LSM tree).
There have been a variety of LSM tree implementations, but many conform to a design in which key-value pairs are accepted into a key-sorted in-memory structure. As that in-memory structure fills, the data is distributed amongst child nodes. The distribution is such that keys in child nodes are ordered within the child nodes themselves as well as between the child nodes. For example, at a first tree-level with three child nodes, the largest key within a left-most child node is smaller than a smallest key from the middle child node and the largest key in the middle child node is smaller than the smallest key from the right-most child node. This structure permits an efficient search for both keys, but also ranges of keys in the data structure.